package day_06;

public class BinarySearchTree<K extends Comparable<K>, V> {
    // 根节点
    private Node root;
    // 节点数
    private int count;

    // 节点定义
    class Node{
        K key;
        V value;
        Node left;
        Node right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public BinarySearchTree() {
        this.root = null;
        this.count = 0;
    }

    public int size(){
        return count;
    }

    public boolean isEmpty(){
        return root == null;
    }

    public void insert(K key, V value){
        root = insert(root, key, value);
    }


    public V searchValue(K k){
        return searchChild(root, k);
    }

    private V searchChild(Node node, K k) {
        if (node == null) return null;
        if (node.key.equals(k)) {
            return node.value;
        }else if(k.compareTo(node.key) > 0){
            return searchChild(node.left, k);
        }else{
            return searchChild(node.right, k);
        }
    }

    public Node searchNode(K k){
        return searchNodeChild(root, k);
    }
    private Node searchNodeChild(Node node, K k) {
        if (node == null) return null;
        if (node.key.equals(k)) {
            return node;
        }else if(k.compareTo(node.key) > 0){
            return searchNodeChild(node.left, k);
        }else{
            return searchNodeChild(node.right, k);
        }
    }


    public boolean contain(K k){
        return containChild(root, k);
    }

    // 在根节点为node的树中是否包含K
    private boolean containChild(Node node, K k) {
        if (node == null) return false;
        if (node.key.equals(k)) {
            return true;
        }else if(k.compareTo(node.key) > 0){
            return containChild(node.left, k);
        }else{
            return containChild(node.right, k);
        }
    }

    // 向以node为根的二叉搜索树中，插入节点(key, Value)
    // 返回插入新节点后的二叉搜索树的根
    private Node insert(Node node, K key, V value) {
        if(node == null) {
            count++;
            return new Node(key, value);
        }
        if(key.equals(node.key)){
            node.value = value;
        }else if(node.key.compareTo(key) > 0){
            node.left = insert(node.left, key, value);
        }else {
            node.right = insert(node.right, key, value);
        }
        return node;
    }
}
